//
// Description: 103. 二叉树的锯齿形层序遍历
// Created by Loading on 2022/5/3.
//

#include <bits/stdc++.h>
#include <Data_Structure_Definition.h>
#include <Utils.h>

using namespace std;

vector<vector<int>> zigzagLevelOrder(TreeNode *root) {
    vector<vector<int>> res;
    if (!root) {
        return res;
    }
    // 是否逆序
    bool isReverse = false;
    queue<TreeNode *> q;
    q.emplace(root);
    while (!q.empty()) {
        int size = q.size();
        vector<int> tmp(size);
        for (int i = 0; i < size; ++i) {
            auto node = q.front();
            q.pop();
            // 逆序则从后向前赋值
            if (isReverse) {
                tmp[size - i - 1] = node->val;
            } else {
                tmp[i] = node->val;
            }
            if (node->left) {
                q.emplace(node->left);
            }
            if (node->right) {
                q.emplace(node->right);
            }
        }
        res.emplace_back(tmp);
        isReverse = !isReverse;
    }

    return res;
}

int main() {
    vector<int> nums{3, 9, 20, -1, -1, 15, 7};
    auto root = generateTreeNode(nums);
    auto res = zigzagLevelOrder(root);
    for (auto &v : res) {
        for (auto x : v) {
            cout << x << ' ';
        }
        cout << endl;
    }

    return 0;
}